//
// Created by 张朝辉 on 2023/9/16.
//

#include "nfa.h"
#include <stack>
#include <iostream>
// 构造函数
NFA::NFA(std::set<std::string> state_set, std::set<char> char_set, std::string start_state, std::set<std::string> final_set,
         std::map<std::pair<std::string, char>, std::set<std::string>> rule_table)
         :state_set(state_set),char_set(char_set),start_state(start_state),final_set(final_set),rule_table(rule_table){}

/*
 * 状态转换函数
 * now_state: 当前的状态, acc_char: 接收的字符
 */
auto NFA::state_transition(std::string now_state,char acc_char) -> std::set<std::string>{
    // 从状态转换表中查找转换后的状态集
    auto it = this->rule_table.find(std::make_pair(now_state,acc_char));
    // 若能查找到转换后的状态集则返回，否则返回一个空集
    if(it != this->rule_table.end()){
        return it->second;
    }
    return {};
}

/*
 * 获取某个状态的ε闭包
 */
auto NFA::getEClosure(std::string state) -> std::set<std::string> {
    // res为当前状态接收ε时发生状态转换后的状态集，'\0'代表ε
    std::set<std::string> res = state_transition(state,'\0');
    // ec保存当前状态的ε-闭包，其中必然包含状态本身
    // es用来接收res中某个状态的ε-闭包
    std::set<std::string> ec{state},es{};
    // 遍历res中的各个状态
    for(auto &re : res){
        es = getEClosure(re);          // 求当前状态的ε-闭包
        ec.insert(es.begin(),es.end());     // 将es结果并入ec中
    }
    return ec;
}
/*
 * 获取某个状态集的ε闭包
 */
auto NFA::getSetEClosure(std::set<std::string> stateSet) -> std::set<std::string> {
    // ec用来保存当前状态集的ε-闭包
    // es用来暂存当前状态集中某个状态的ε-闭包
    std::set<std::string> ec{},es{};
    for(auto &state : stateSet){
        es = getEClosure(state);
        ec.insert(es.begin(),es.end());
    }
    return ec;
}

/*
 * 获取某个状态集接收到某个字符后发生状态转换后的状态集
 * s: 状态集, c: 接收的字符
 */
auto NFA::stateSet_transition(std::set<std::string> s, char c) -> std::set<std::string> {
    std::set<std::string> k{},m{};
    for(auto &x : s){
        // m = state_transition(x,c);
        m = getSetEClosure(state_transition(x,c));
        k.insert(m.begin(),m.end());
    }
    return k;
}

/*
 * 扩展状态转换函数（非递归）
 * now_state: 当前的状态, acc_str: 接收的字符串
 */
auto NFA::extend_state_transition(std::string now_state,std::string acc_str) -> std::set<std::string>{
    // 变量s表示当前的状态集
    std::set<std::string> s = getEClosure(now_state);    // 接收空字符ε，将当前状态插入到状态集中
    int i = 0,len = acc_str.length();
    // 依次遍历字符串中的各个字符
    while (i < len){
        s = stateSet_transition(s,acc_str[i]);
        i++;
    }
    return s;
}

/*
 *  递归地获取所有经过状态转换后得到的状态集，将其存入状态集的集合s中,s1为初始状态集
 */
auto NFA::getAllStateSet(std::set<std::set<std::string>> &s,std::set<std::string> s1) -> void {
    std::set<std::string> k{};
    for(auto &ch: char_set){
        k = stateSet_transition(s1,ch);
        if(s.find(k) == s.end()){
            s.insert(k);
            getAllStateSet(s,k);
        }
    }
}

/*
 *  判断两个集合的交集是否为空
 */
auto NFA::setIntersectionIsEmpty(std::set<std::string> s1, std::set<std::string> s2) -> bool {
    int len = s1.size() + s2.size();
    s2.insert(s1.begin(),s1.end());
    if(len == s2.size())return true;
    return false;
}

/*
 * 判断某个字符串能否被此NFA所接受
 */
auto NFA::isAccept_str(std::string str) -> bool {
    auto res = extend_state_transition(start_state,str);
    return !setIntersectionIsEmpty(final_set,res);
}

int NFA::state_num = 0;
/*
 * 每次获取一个新的状态值
 */
auto NFA::getNewState() -> std::string {
    return "state"+std::to_string(state_num++);
}

/*
 *  通过子集构造法将一个NFA转换为与之等价的DFA
 */
auto NFA::NFA2DFA() -> DFA {
    // 状态集的集合，其中的某个状态集对应于DFA中的某个状态
    std::set<std::set<std::string>> s;
    // 状态转换表，存储从一个状态集接收某个状态后转换到另一个状态集
    std::map<std::pair<std::set<std::string>,char>,std::set<std::string>> table;
    std::set<std::string> st = getEClosure(start_state);     // 初始状态集
    s.insert(st);
    getAllStateSet(s, st);
    // 状态集到DFA中某个状态的对照表
    std::map<std::set<std::string>,std::string> t2;
    std::set<std::string> fin_set;
    std::set<std::string> cs;    // DFA的状态集
    std::string z;
    for(auto &w: s){
        z = getNewState();
        t2[w] = z;
        if(!setIntersectionIsEmpty(w,final_set)){
            fin_set.insert(z);
        }
        cs.insert(z);
    }
    std::map<std::pair<std::string,char>,std::string> transition_table;   // DFA状态转换表
    std::set<std::string> k{};
    for(auto &w: s){
        for(auto &ch: char_set){
            k = stateSet_transition(w,ch);
            table[std::make_pair(w,ch)] = k;
            transition_table[std::make_pair(t2.find(w)->second,ch)] = t2.find(k)->second;
        }
    }

    return DFA(cs, char_set, t2.find(st)->second, fin_set, transition_table);
}

/*
 * 正则表达式为单个字符的情况下将其转换为NFA
 */
auto NFA::singleChar2NFA(char ch) -> NFA {
    std::map<std::pair<std::string,char>,std::set<std::string>> rt;   // 状态转换表
    std::string start = getNewState(),final = getNewState();
    rt[std::make_pair(start,ch)] = {final};
    return NFA({start,final}, {ch}, start, {final}, rt);
}

/*
 * 合并两个NFA，返回一个新的NFA，op为具体的合并方式，包括(./+)
 */
auto NFA::combineNFA(NFA n1, NFA n2,char op) -> NFA {
    n1.state_set.insert(n2.state_set.begin(),n2.state_set.end());     // 合并状态集
    n1.char_set.insert(n2.char_set.begin(),n2.char_set.end());        // 合并字符集
    n1.rule_table.insert(n2.rule_table.begin(),n2.rule_table.end());   // 合并规则表
    if(op == '.'){
        for(auto &q: n1.final_set){         // 遍历n1终态集中的每个状态
            auto it = n1.rule_table.find(std::make_pair(q,'\0'));
            if(it != n1.rule_table.end()){
                it->second.insert(n2.start_state);
            }else{
                n1.rule_table[std::make_pair(q,'\0')] = {n2.start_state};
            }
        }
        return {n1.state_set,n1.char_set,n1.start_state,n2.final_set,n1.rule_table};
    }
    if(op == '+'){
        std::string newStartState = getNewState();
        n1.rule_table[std::make_pair(newStartState,'\0')] = {n1.start_state,n2.start_state};
        n1.final_set.insert(n2.final_set.begin(),n2.final_set.end());
        return {n1.state_set,n1.char_set,newStartState,n1.final_set,n1.rule_table};
    }
    throw "NFA合并失败";
}

/*
 * 为某个NFA增加repeat功能
 */
auto NFA::addStartOp(NFA nfa) -> NFA {
    for(auto &f: nfa.final_set){
        auto it = nfa.rule_table.find(std::make_pair(f,'\0'));
        if(it != nfa.rule_table.end()){
            it->second.insert(nfa.start_state);
        }else{
            nfa.rule_table[std::make_pair(f,'\0')] = {nfa.start_state};
        }
    }
    std::string newStartState = getNewState();
    nfa.state_set.insert(newStartState);
    nfa.rule_table[std::make_pair(newStartState,'\0')] = {nfa.start_state};
    nfa.start_state = newStartState;
    nfa.final_set.insert(newStartState);
    return nfa;
}

/*
 * 返回两个运算符的优先级
 * 在Re2NFA中，op1为运算符栈顶符号，op2为串中待入栈的运算符
 */
auto NFA::operatorPriority(char op1, char op2) -> char {
    std::map<std::pair<char,char>,char> opPriorityTable;           // 构造一个算符优先表,懒得化简
    opPriorityTable[std::make_pair('+','+')] = '>';
    opPriorityTable[std::make_pair('+','.')] = '<';
    opPriorityTable[std::make_pair('+','*')] = '<';
    opPriorityTable[std::make_pair('+','(')] = '<';
    opPriorityTable[std::make_pair('+',')')] = '>';
    opPriorityTable[std::make_pair('+','#')] = '>';

    opPriorityTable[std::make_pair('.','+')] = '>';
    opPriorityTable[std::make_pair('.','.')] = '>';
    opPriorityTable[std::make_pair('.','*')] = '<';
    opPriorityTable[std::make_pair('.','(')] = '<';
    opPriorityTable[std::make_pair('.',')')] = '>';
    opPriorityTable[std::make_pair('.','#')] = '>';

    opPriorityTable[std::make_pair('*','+')] = '>';
    opPriorityTable[std::make_pair('*','.')] = '>';
    opPriorityTable[std::make_pair('*','*')] = '>';
    opPriorityTable[std::make_pair('*','(')] = '#';      // 说明运算符关系不合法
    opPriorityTable[std::make_pair('*',')')] = '>';
    opPriorityTable[std::make_pair('*','#')] = '>';

    opPriorityTable[std::make_pair('(','+')] = '<';
    opPriorityTable[std::make_pair('(','.')] = '<';
    opPriorityTable[std::make_pair('(','*')] = '<';
    opPriorityTable[std::make_pair('(','(')] = '<';
    opPriorityTable[std::make_pair('(',')')] = '=';
    opPriorityTable[std::make_pair('(','#')] = '#';    // 不存在

    opPriorityTable[std::make_pair(')','+')] = '>';
    opPriorityTable[std::make_pair(')','.')] = '>';
    opPriorityTable[std::make_pair(')','*')] = '>';
    opPriorityTable[std::make_pair(')','(')] = '#';     // 不存在)(,应为).(或)+(
    opPriorityTable[std::make_pair(')',')')] = '#';     // 不应存在))
    opPriorityTable[std::make_pair(')','#')] = '>';

    opPriorityTable[std::make_pair('#','+')] = '<';
    opPriorityTable[std::make_pair('#','.')] = '<';
    opPriorityTable[std::make_pair('#','*')] = '<';
    opPriorityTable[std::make_pair('#','(')] = '<';
    opPriorityTable[std::make_pair('#',')')] = '#';
    opPriorityTable[std::make_pair('#','#')] = '=';
    auto it = opPriorityTable.find(std::make_pair(op1,op2));
    if(it != opPriorityTable.end()){
        return it->second;
    }
    throw "正则表达式有误";
}

/*
 * 将一个正则表达式转换为NFA，参数正则表达式re应当是一个正则表达式的正确表示方式，本函数不检查正则表达式的正确性
 * 构造NFA的过程核心为构造NFA的状态转换规则
 */
auto NFA::Re2NFA(std::string re) -> NFA {
    if(re.length() == 0){
        std::string q = getNewState();
        return NFA({q},{},q,{q}, {});
    }
    std::stack<char> op_stack;    // 运算符栈
    std::stack<NFA> nfa_stack;     // nfa栈
    op_stack.push('#');                 // 初始化栈底符号
    std::string ops = "*().+#";
    std::string rex = re + '#';
    int i = 0;
    while (i<rex.length()){
        if(ops.find(rex[i]) == -1){          // 不是运算符，说明是字符
            nfa_stack.push(singleChar2NFA(rex[i]));
            i++;
        }else{
            if(operatorPriority(op_stack.top(),rex[i]) == '>'){      // 栈顶算符优先级大于当前算符
                if(op_stack.top() == '*'){
                    char nowOp = op_stack.top();
                    op_stack.pop();
                    NFA a = nfa_stack.top();
                    nfa_stack.pop();
                    nfa_stack.push(addStartOp(a));
                }else{
                    char nowOp = op_stack.top();
                    op_stack.pop();
                    NFA b = nfa_stack.top();
                    nfa_stack.pop();
                    NFA a = nfa_stack.top();
                    nfa_stack.pop();
                    nfa_stack.push(combineNFA(a,b,nowOp));
                }
            }else if(operatorPriority(op_stack.top(),rex[i]) == '='){
                op_stack.pop();
                i++;
            }else if(operatorPriority(op_stack.top(),rex[i]) == '<'){
                op_stack.push(rex[i]);
                i++;
            } else{
                throw "正则表达式有误";
            }
        }
    }
    auto result = nfa_stack.top();       // 正常状况下，NFA栈的栈顶为最终构造的NFA且栈中只含有一个元素
    nfa_stack.pop();
    if(nfa_stack.empty()){
        return result;
    }
    throw "正则表达式有误";
}

auto NFA::description() -> void {
    std::cout<<"--------------------------------------当前NFA详情----------------------------------------"<<std::endl;
    std::cout<<"状态集：{ ";
    for(auto &s: state_set){
        std::cout<<s<<" ";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"字符集：{ ";
    for(auto &s: char_set){
        std::cout<<s<<" ";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"开始状态："<<start_state<<std::endl;
    std::cout<<"接受状态集：{ ";
    for(auto &s: final_set){
        std::cout<<s<<" ";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"状态转换表：{ ";
    for(auto &r: rule_table){
        std::cout<<"δ("<<r.first.first<<","<<r.first.second<<") = { ";
        for(auto &s: r.second){
            std::cout<<s<<" ";
        }
        std::cout<<"}\t";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"----------------------------------------------------------------------------------------"<<std::endl;
}









